package midalgorithms.backtrack;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _01LetterCombinations {
    /**
     *  回溯模版
     * void backtrack(参数){
     *     if(终止条件){
     *         存放结果;
     *         return;
     *     }
     *     for(选择：本层集合中元素（树中节点孩子的数量就是集合的大小）){
     *         处理结点;
     *         backtrack(路径,选择列表);
     *         回溯，撤销处理结果;
     *     }
     * }
     */
    public static List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() == 0){
            return res;
        }
        Map<Character,String> map = new HashMap<>();
        map.put('2',"abc");
        map.put('3',"def");
        map.put('4',"ghi");
        map.put('5',"jkl");
        map.put('6',"mno");
        map.put('7',"pqrs");
        map.put('8',"tuv");
        map.put('9',"wxyz");
        backtrack(res,map,digits,0,new StringBuilder());
        return res;
    }

    private static void backtrack(List<String> res, Map<Character, String> map, String digits, int index, StringBuilder combination) {
        if (index == digits.length()){
            //  存放结果
            res.add(combination.toString());
            return;
        }
        char nowDigit = digits.charAt(index);
        String values = map.get(nowDigit);
        for (int i = 0;i < values.length();i++){
            combination.append(values.charAt(i));
            backtrack(res,map,digits,index+1,combination);
            combination.deleteCharAt(index);
        }
    }
}
